package com.xiayuanxing.arithmetic.Kmp;

import java.util.ArrayList;

/**
 * @projectName: arithmetic
 * @className: KMPAlgorithm
 * @author: xiayuanxing
 * @description: KMP算法
 * @date: 2021/11/10 16:24
 * @version: 1.0
 */
public class KMPAlgorithm {

    public static void main(String[] args) {

        String s1 = "暴力匹配算法 夏s远s兴暴力匹 配夏远兴算法暴力 匹配算法";
        String s2 = "夏远兴";

        int encapsulation = encapsulation(s1, s2);
        System.out.println("encapsulation==>"+encapsulation);

    }

    /**
     * @param str1:
     * @param str2:
     * @return int
     * @author xiayuanxing
     * @description 封装
     * @date 2021/11/11 14:21
     */
    public static int encapsulation(String str1,String str2){
        int[] next = kmpNext(str1);
        int search = kmpSearch(str1, str2, next);
        return search;
    }

    /**
     *
     * @param str1 源字符串
     * @param str2 要匹配的字符串
     * @param next 部分匹配表
     * @return
     */
    public static int kmpSearch(String str1,String str2,int[] next){
        for (int i = 0,j = 0; i < str1.length(); i++) {

            //kmp算法核心点
            while (j > 0 && str1.charAt(i) != str2.charAt(j)){
                j = next[j - 1];
            }

            if (str1.charAt(i) == str2.charAt(j)){
                j++;
            }
            if (j == str2.length()){
                //找到了
                return i - j + 1;
            }
        }
        return -1;
    }

    /**
     * @param dest:
     * @return int
     * @author xiayuanxing
     * @description 获取一个字符串的部分匹配表
     * @date 2021/11/10 16:40
     */
    public static int[] kmpNext(String dest){
        //创建一个数组用来保存部分匹配值
        int[] next = new int[dest.length()];
        //如果字符串长度为1，部分匹配值就是0
        next[0] = 0;
        for (int i = 1,j = 0; i < dest.length(); i++) {
            //当dest.charAt(i) != dest.charAt(j) 时，我们需要从next[j -1]获取新的j
            //当我们发现有dest.charAt(i) == dest.charAt(j)成立才退出
            //kmp算法核心点
            while (j > 0 && dest.charAt(i) != dest.charAt(j)){
                j = next[j - 1];
            }
            //当dest.charAt(i) == dest.charAt(j)时，部分匹配值就是+1
            if (dest.charAt(i) == dest.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}
